class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int max_len = ranges::max(wordDict, {}, &string::length).length();
        unordered_set<string> words(wordDict.begin(), wordDict.end());

        int n = s.length();
        vector<int> memo(n + 1, -1); // -1 表示没有计算过
        auto dfs = [&](auto& dfs, int i) -> bool {
            if (i == 0) { // 成功拆分！
                return true;
            }
            int& res = memo[i]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            for (int j = i - 1; j >= max(i - max_len, 0); j--) {
                if (words.count(s.substr(j, i - j)) && dfs(dfs, j)) {
                    return res = true; // 记忆化
                }
            }
            return res = false; // 记忆化
        };
        return dfs(dfs, n);
    }
};